0% completed
Problem Statement
You are given an array of integers nums, and integer k, size of the sliding window which moves from the very left to the very right in the array. In each window, you can have only k numbers, and the window moves one position right by each time.
Return the array containing the maximum element of each sliding window.
Examples
Example 1:
- Input: nums = [2, 1, 5, 1, 3, 2], k = 3
- Expected Output: [5, 5, 5, 3]
- Justification: Here, the window of size 3 moves across the array. The maximum values in each window are 5 (from [2, 1, 5]), 5 (from [1, 5, 1]), 5 (from [5, 1, 3]), and 3 (from [1, 3, 2]).
Example 2:
- Input: nums = [4, -2, -3, 4, 1], k = 2
- Expected Output: [4, -2, 4, 4]
- Justification: The maximum values in each window of size 2 are 4 (from [4, -2]), -2 (from [-2, -3]), 4 (from [-3, 4]), and 4 (from [4, 1]).
Example 3:
- Input: nums = [9, 7, 2, 4, 6], k = 4
- Expected Output: [9, 7]
- Justification: In this case, there are only two windows of size 4. The maximum value in the first window is 9 (from [9, 7, 2, 4]), and in the second window is 7 (from [7, 2, 4, 6]).
Constraints:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
Solution
To solve this problem, we'll use a deque (double-ended queue) to maintain the indices of the elements in the current window, ensuring the deque always has the maximum element's index at the front. This approach works because it allows us to efficiently remove elements that are no longer in the window (by checking if they are out of the current window's range) and ensure the first element in the deque is always the maximum of the current window. We'll iterate through the array, adding each element's index to the deque while maintaining these properties.
This method is effective because it combines the efficiency of a queue for managing the window's sliding mechanism with the ability to quickly update and retrieve the maximum value. By only storing relevant indices and removing those that are no longer in the window or are not potential maximums, we significantly reduce the time complexity compared to brute force methods that check every window's maximum separately.
Step-by-step Algorithm
- Initialize an empty deque
Dto store indices of array elements. - Iterate through each element of the array
nums:- If
Dis not empty and the front element ofDis out of the current window's range (i - k), pop it from the front. - While
Dis not empty and the current element is greater than the element at the back ofD, pop elements from the back. This ensures that the first element inDis always the maximum of the current window. - Add the current index
ito the back ofD. - If
iis greater than or equal tok - 1, append the front element ofDto the result array, as the window has now reached its full size.
- If
- Return the result array containing the maximums.
Algorithm Walkthrough
Let's consider the input: nums = [2, 1, 5, 1, 3, 2], k = 3
-
Initialization:
- The deque
Dis initialized as empty. - An empty result array is initialized to store the maximum of each window.
- The deque
-
Iteration 1 (i = 0, nums[i] = 2):
- Since
Dis empty, add index0toD. Dnow contains[0].- The window has not yet reached its full size (
k = 3), so we don't add anything to the result array.
- Since
-
Iteration 2 (i = 1, nums[i] = 1):
- No indices are removed from
Dsince all indices inDare within the current window's range. nums[i]is less thannums[D.back()](1 < 2), so just add index1toD.Dnow contains[0, 1].- The window has not reached its full size, so no action on the result array.
- No indices are removed from
-
Iteration 3 (i = 2, nums[i] = 5):
- No indices are removed from
Dfor being out of range. nums[i]is greater thannums[D.back()], so remove indices fromDwhilenums[i]is greater thannums[D.back()]. Remove0and1fromD.- Add index
2toDsincenums[2]is now the greatest so far. Dnow contains[2].- The window has reached its full size. Add
nums[D.front()](which is5) to the result array.
- No indices are removed from
-
Iteration 4 (i = 3, nums[i] = 1):
- No indices are removed from
Dfor being out of range. nums[i]is less thannums[D.back()], so just add index3toD.Dnow contains[2, 3].- Add
nums[D.front()](which is still5) to the result array since the window is full.
- No indices are removed from
-
Iteration 5 (i = 4, nums[i] = 3):
- No indices are removed from
Dfor being out of range. nums[i]is greater thannums[D.back()](the index atD.back()is3, andnums[3]is1), so remove index3fromD.- Add index
4toD. Dnow contains[2, 4].- Add
nums[D.front()](which is5) to the result array.
- No indices are removed from
-
Iteration 6 (i = 5, nums[i] = 2):
- Remove index
2fromDsince it's out of the current window's range (i - k + 1 = 3). nums[i]is less thannums[D.back()], so just add index5toD.Dnow contains[4, 5].- Add
nums[D.front()](which is3) to the result array.
- Remove index
-
Final Result:
- The result array, which contains the maximum of each window, is
[5, 5, 5, 3].
- The result array, which contains the maximum of each window, is
Code
Complexity Analysis
Time Complexity
: Each element in the array is processed exactly twice - once when it's added to the deque and once when it's removed. This leads to a linear time complexity because the operations of adding to and removing from the deque (or its equivalent data structure) are O(1) operations.
Space Complexity
: In the worst-case scenario, the space complexity is due to the storage requirements of the result array, which contains at most N - k + 1 elements. The deque (or similar structure) itself will have at most k elements because it only stores elements from the current window. However, since k is a constant that does not scale with the input size N, the dominant term for space complexity is due to the output array, making it .
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity